9020. Split into k sub-arrays

 

Given array of n elements and number k. Split the given array into k sub-arrays (they must cover all the elements). The maximum sub-array sum achievable out of k sub-arrays formed, must be minimum possible. Find that possible sub-array sum.

 

Input. First line contains two numbers n and k (n ≤ 106, 1 ≤ k ≤ n). Second line contains n positive integers, each no more than 109.

 

Output. Print the minimum possible sub-array sum.

 

Explanation. For the first sample the optimal split is {1, 2}, {3}, {4}. Maximum sum of all sub-arrays is 4, which is minimum possible for 3 subarrays.

For the second sample the optimal split is {1, 2, 3, 4}, {2, 3, 4}, {2, 3, 1}. Maximum sum of all sub-arrays is 10, which is minimum possible for 3 subarrays.

 

Sample input 1

Sample output 1

4 3

1 2 3 4

4

 

 

Sample input 2

Sample output 2

10 3

1 2 3 4 2 3 4 2 3 1

10

 

 

SOLUTION

binary search

 

Algorithm analysis

The answer can be found by the binary search. Obviously, it is not less than 1 (the integers in array are positive) and no more than the sum of all numbers. Set left = 1, right = the sum of the numbers in the array. Then the minimum possible sub-array sum lies on the interval [left; right].

Consider a subproblem: is it possible to split an array into k subarrays so that the maximum of the sums of all k subarrays will be no more than s0. If array contains at least one element greater than s0, then such partition is impossible. Split the original array into subarrays, the sum of which elements is no more than s0. If there are no more than k such subarrays, the split is possible.

 

Example

Consider in the second example the required partitions into subarrays for different values of s0:

 

Algorithm realization

Declare the constant MAX = 106 and array m.

 

#define MAX 1000000

int m[MAX];

 

Function f returns 1 if it is possible to split array into k subarrays so that the maximum sums of all k subarrays is no more than s0.

 

int f(long long s0)

{

  long long sum = 0;

  int cnt = 1;

  for (int i = 0; i < n; i++)

  {

 

If some element of array is greater than s0, the partition is impossible.

 

    if (m[i] > s0) return 0;

 

Compute the sum of the current subarray.

 

    sum += m[i];

 

As soon as the current sum becomes greater than s0, the number of subarrays cnt is increased by 1 and we start to calculate the sum of the next subarray.

 

    if (sum > s0)

    {

      sum = m[i];

      cnt++;

    }

  }

 

If an array can be split into at most k subarrays, then it can be split into k (k ≤ n) subarrays.

 

  if (cnt <= k) return 1;

  return 0;

}

 

The main part of the program. Read the input data. Find the sum of numbers in array in the variable right.

 

scanf("%d %d", &n, &k);

left = 1; right = 0;

for (i = 0; i < n; i++)

{

  scanf("%d", &m[i]);

  right += m[i];

}

 

The minimum possible sub-array sum lies in the interval [left; right]. Start the binary search.

 

while (left < right)

{

  mid = (left + right) / 2;

  if (f(mid) == 1)

    right = mid;

  else

    left = mid + 1;

}

 

Print the answer.

 

printf("%lld\n", left);